#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE  20
typedef int Elemtype;
typedef struct BiTNode{
    Elemtype data;
    struct BiTNode *lchild;
    struct BiTNode * rchild;
}BiTNode,*BiTree;
/********           队列的初始化及操作                   */ 
//队列元素
typedef struct node
{
    BiTNode* data;
    int level; //新增一个成员是表示该节点的层级
    struct node *next;
}QElemType;//改名为QElemType
//队列结构
typedef struct Queue{
    QElemType *front;
    QElemType *rear;
}Queue;
//初始化一个队列节点指针
QElemType* initQNode(){
    QElemType *n = (QElemType*)malloc(sizeof(QElemType));
    return n; 
}
//初始化队列
Queue* initQueue(){
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = NULL;
    q->rear = NULL;
    return q;
}
int isEmpty(Queue *q){
    if(q->front ==NULL){
        return 1;
    }
    return 0;
}

//入队  现在将传参改成了传一个队列节点元素的指针，而不是树节点指针
void EnQueue(Queue*q,QElemType* Qnode){
    QElemType * node = initQNode();
    node->data = Qnode->data;
    node->level = Qnode->level;
    node->next = NULL;
  
    if(isEmpty(q)){
        q->front = node;
        q->rear = node;
    }else{
        q->rear->next = node;
        q->rear = node;
    }
}

//出队  更新为返回一个队列元素的指针
QElemType * DeQueue(Queue *q){
    QElemType * node = q->front;
    if(isEmpty(q)){
        return NULL;
    }
    if(q->front == q->rear){
        q->front = NULL;
        q->rear = NULL;
    }else{
        q->front = q->front->next;
    }
    return node;
}
/********           树的创建和递归遍历                   */ 
void visit(Elemtype data){
    printf("  %d  ",data);
}
void preOrder(BiTree T){
    if(T!=NULL){
    visit(T->data);
    preOrder(T->lchild);
    preOrder(T->rchild);
    }
}
void inOrder(BiTree T){
 if(T!=NULL){
    inOrder(T->lchild);
    visit(T->data);
    inOrder(T->rchild);
    }
}

void postOrder(BiTree T){
 if(T!=NULL){
    postOrder(T->lchild);
    postOrder(T->rchild);
    visit(T->data);
    }
}
//层次遍历
void levelTraverse(BiTree T){
        Queue *Q = initQueue();
        
        if(T!=NULL){
            QElemType* Qnode = initQNode();
            Qnode->data = T;
            EnQueue(Q,Qnode);
        }
        while (!isEmpty(Q))
        {
           BiTNode * e = DeQueue(Q)->data; //这里直接拿队列元素节点的data也就是树节点指针
           visit(e->data);
           if(e->lchild!=NULL){
            QElemType* Qnode = initQNode();
            Qnode->data = e->lchild;
            EnQueue(Q,Qnode);
           }
           if(e->rchild!=NULL){
            QElemType* Qnode = initQNode();
            Qnode->data = e->rchild;
            EnQueue(Q,Qnode);
           }
        }
}

//通过中序遍历和先序遍历来创建二叉树
BiTNode * createBiTree(Elemtype preOrderarr[],int preFirst,int preLast,
 Elemtype inOrderarr[],int inFirst , int inLast){

        if(preFirst > preLast){
            return NULL;
        }
        BiTNode * root = (BiTNode *)malloc(sizeof(BiTNode));
        root->data = preOrderarr[preFirst];
        int rootIndex; //寻找根节点在中序序列的索引
        for ( rootIndex = inFirst; rootIndex <= inLast; rootIndex++)
        {
           if(root->data == inOrderarr[rootIndex]){
                break;
           }
        }
        BiTNode * lchild = createBiTree(preOrderarr,preFirst+1,preFirst+rootIndex-inFirst,
        inOrderarr,inFirst,rootIndex-1);
        BiTNode * rchild = createBiTree(preOrderarr,preFirst+rootIndex-inFirst+1,preLast,
        inOrderarr,rootIndex+1,inLast);
        root->lchild = lchild;
        root->rchild = rchild;
        return root;
}

//层次遍历 + 中序遍历确定二叉树
BiTree createBiTree02(Elemtype levelOrderarr[],int levelFirst,int levelLast,
 Elemtype inOrderarr[],int inFirst , int inLast){

    if(levelFirst > levelLast){
        return NULL;
    }
    //每次递归确定一个根节点
    BiTNode * root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data = levelOrderarr[levelFirst];
    //在中序遍历中寻找根节点的位置，划分左右子树
    int rootIndex =  inFirst;
    for (; rootIndex <= inLast; rootIndex++)
    {
       if(inOrderarr[rootIndex] == root->data){
        break;
       }
    }  
    //层次遍历中左右子树的遍历序列和先序序列分别相等
    //使用两个数组，分别存储层次遍历中的左子树遍历的序列和右子树遍历的序列
    Elemtype leftLevelOrderList[MAXSIZE];
    int leftLength = 0;
    //遍历中序序列对比找到左子树的所有元素
    for (int i = levelFirst + 1; i <= levelLast; i++)
    {
        for (int j = inFirst; j <= rootIndex; j++)
        {
           if(levelOrderarr[i] == inOrderarr[j]){
                leftLevelOrderList[leftLength++] = levelOrderarr[i]; 
           }
        }
    }
    Elemtype rightLevelOrderList[MAXSIZE];
    int rightLength = 0;
    //遍历中序序列对比找到右子树的所有元素
    for (int i = levelFirst + 1; i <= levelLast; i++)
    {
        for (int j = rootIndex+1; j <= inLast; j++)
        {
           if(levelOrderarr[i] == inOrderarr[j]){
                rightLevelOrderList[rightLength++] = levelOrderarr[i]; 
           }
        }
    }
    //递归创建左右子树的根节点
    root->lchild = createBiTree02(leftLevelOrderList,0,leftLength-1,inOrderarr,inFirst,rootIndex-1);
    root->rchild = createBiTree02(rightLevelOrderList,0,rightLength-1,inOrderarr,rootIndex+1,inLast);
    return root;
}

/********           栈的初始化及相关操作                   */ 
//栈的初始化
typedef struct SqStack
{
   BiTNode * data[MAXSIZE];
   int top;
}SqStack, *Stack;
//创建栈
Stack initStack(){
    Stack s;
    s = (Stack)malloc(sizeof(SqStack));
    s->top = -1;
    return s;
}
//栈空
int isStackEmpty(Stack s){
    if(s->top == -1){
        return 1;
    }
    return 0;
}
//入栈
void push(Stack s,BiTNode* p){
    s->top++;
    s->data[s->top] = p;
}
//出栈
void pop(Stack s,BiTNode** p){
    *p = s->data[s->top];
    s->top--;
}

/********           树的非递归遍历                   */ 
//先序非递归遍历
void preOrder02 (BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode!=NULL || !isStackEmpty(stack))
    {
       if(pNode){
            push(stack,pNode);
            visit(pNode->data);
            pNode = pNode->lchild;
       }else{
            pop(stack,&pNode);
            pNode = pNode->rchild;
       }
    }
}
//中序非递归遍历
void inOrder02 (BiTree T){
    BiTNode *pNode = T;
    Stack stack = initStack();
    while (pNode!=NULL || !isStackEmpty(stack))
    {
       if(pNode){
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
            pop(stack,&pNode);
            visit(pNode->data);
            pNode = pNode->rchild;
       }
    }
}
//后序非递归遍历 
//左子树- 右子树 - 根
void postOrder02(BiTree T){
    BiTNode *pNode = T; 
    BiTNode *r = NULL; //这个r是最后访问的节点，用来判断某个根节点pnode的右子树是否被访问,因为右子树访问结束之后，最后 一个被访问的节点一定是右子树的根节点，也就是pnode的右孩子。
    Stack stack = initStack();
    while (pNode!= NULL || !isStackEmpty(stack))
    {
       if(pNode){
        //寻找最左下的节点
            push(stack,pNode);
            pNode = pNode->lchild;
       }else{
         //先获取栈中最顶上的节点，看他有没有右子树
          pop(stack,&pNode);//此时 pNode 是 左子树已经访问完毕的树的根节点
          push(stack,pNode);
          if(pNode->rchild && pNode->rchild!= r){
            // 右子树是存在的且右子树没有被访问过，那么先访问右子树再访问根节点
            pNode = pNode->rchild; //切换到右子树的根节点
            push(stack,pNode);//对于一个子树来说，根是最后访问的，先访问左子树
            pNode = pNode->lchild;//切换到左子树的根节点
          }else{
            //如果右子树为空或者右子树已经访问过了，那就访问根节点
            pop(stack,&pNode);
            visit(pNode->data);
            r = pNode;
            pNode = NULL; //当前被打印的节点一定是子树的根节点
            /*
            如果是左子树的根节点 ： 那么某个树的左子树被遍历完了，就要看他有没有右子树要遍历
            如果是右子树的根节点：  那么某个树的右子树被遍历完了，就要遍历他自己了
            */
          }
       }
    }
}
/********           二叉树应用题                   */ 
//求二叉树的节点数量
int getTreeNodes(BiTree T){
    if(T== NULL){
        return 0;
    }
    return getTreeNodes(T->lchild) + getTreeNodes(T->rchild) +1;
}
//求叶子节点数量
int getLeaveNodes(BiTree T){
    if(T == NULL){
        return 0;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        return 1;
    }
    return getLeaveNodes(T->lchild) + getLeaveNodes(T->rchild);
}
/*
是否为空树
    空树  -不影响结果
    非空树  分类根据题目要求
          度为0
          度为1
          度为2  
*/
//统计度为1的节点数
int getSingleDegreeNode(BiTree T){
    if(T == NULL){
        return 0;
    }else if (T->lchild != NULL && T->rchild==NULL)
    {
       return 1 + getSingleDegreeNode(T->lchild);
    }else if (T->lchild == NULL && T->rchild!=NULL)
    {
       return 1 + getSingleDegreeNode(T->rchild);
    }else{
        //度为2或者度为0
        return getSingleDegreeNode(T->lchild) +getSingleDegreeNode(T->rchild);
    }
}
//求值为x的节点的位置
BiTNode * getXNode(BiTree T,Elemtype x){
    if(T==NULL){
        return NULL;
    }
    else if (T->data == x)
    {
      return T;
    }else{
      BiTNode * leftRes = getXNode(T->lchild,x);
      if(leftRes!=NULL){
        return leftRes;
      }  
      return getXNode(T->rchild,x);
    }
}
//求树的高度
int getHeight(BiTree T){
    if(T == NULL){
        return 0;
    }
    int leftHeight = getHeight(T->lchild);
    int rightHeight =getHeight(T->rchild);
    int res = leftHeight > rightHeight ? leftHeight :rightHeight;
    return  res + 1;
}
//求x子树在树的深度
int getXHeight(BiTree T,Elemtype x){
    BiTNode* xNode  = getXNode(T,x);
    int res = getHeight(xNode);
    return res;
}
/*
1.分析边界条件
2.假设子树调用的结果就是正确的
3.分解问题，并保证利用 2.的结果使得本层是正确的
*/
//交换左右子树
void swithLeftandRight(BiTree T){
    if(T==NULL){
        return;
    }
    swithLeftandRight(T->lchild);
    swithLeftandRight(T->rchild);
    BiTNode * temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;
}
//判断两棵树是否相似
int isSimilar(BiTree T1,BiTree T2){
    if(T1==NULL && T2==NULL){
        return 1;
    }
    if(T1!=NULL && T2!=NULL){
        return isSimilar(T1->lchild,T2->lchild) && isSimilar(T1->rchild,T2->rchild);
    }
    return 0;
}
//初始化双链表头节点
BiTNode * initLinkNode(){
    BiTNode * head = (BiTNode*)malloc(sizeof(BiTNode));
    head->lchild = NULL;
    head->rchild = NULL;
    return head;
}
//将所有叶子节点串联成头结点双链表
void LeafLinkList(BiTree T,BiTNode ** pTail){ //3  0
    if(T!=NULL){
        if(T->lchild == NULL && T->rchild == NULL){
            (*pTail)->rchild = T;
            T->lchild =  (*pTail);
            (*pTail)= T;
        }else{
        LeafLinkList(T->lchild,pTail);//6 插入->pTail更新
        LeafLinkList(T->rchild,pTail);//7  插入在6的后面->pTail此时指向6
        } 
    }
}
//与上一个函数一起的，调用叶子节点链表的函数
void operateFun(BiTree T){
    //初始化头结点
    BiTNode * L = initLinkNode();
    BiTNode * pTail = L;
    //串联叶子节点
    LeafLinkList(T,&pTail);
    BiTNode*pNode = L->rchild;
    while (pNode!=NULL)
    {
       printf(" %d ",pNode->data);
       pNode = pNode->rchild;
    }
    printf("\n");
    
}
//计算函数
int operator(char oprt,int left,int right){
    switch (oprt)
    {
    case '+':
    return left + right;
    break;
    
    case '-':
    return left - right;
    break;

    case '*':
    return left * right;
    break;

    case '/':
    return left / right;
    break;

    default:
        break;
    }
}
/*
假设 子树的表达式的值已经被正确计算了
分解情况：要先计算左子树，然后是右子树，然后是根节点,处理根就是调用计算符
    1.如果叶子结点，它的data就是一个值，data-'0'
    2.如果非叶子节点，直接当做一个子树。
*/
//后序遍历计算表达式的值
int getRes(BiTree T){
    if(T==NULL){
        return 0;
    }
    if(T->lchild == NULL && T->rchild == NULL){
        return T->data -'0';
    }
    int leftRes = getRes(T->lchild);
    int rightRes = getRes(T->rchild);
    return operator(T->data,leftRes,rightRes);

}

//最大宽度
int getWeight(BiTree T){
    if(T==NULL){
        return 0;
    }
    Queue *Q = initQueue();
    QElemType e;
    e.data = T;
    e.level = 1;
    EnQueue(Q,&e);
    int maxNum = 0;
    int levelNum = 0;
    int current = 1;
    while (!isEmpty(Q))
    {
       QElemType *Qnode =  DeQueue(Q);
       
       if(current == Qnode->level){
        //printf(" %d ",Qnode->data->data);
        levelNum ++;
       }else{
        if(maxNum < levelNum){
            maxNum = levelNum;
            current = Qnode->level;
            levelNum = 1;
        }
       }
        if(Qnode->data->lchild !=NULL){
            QElemType temp;
             
            temp.data = Qnode->data->lchild;
         //   printf("left: %d ",temp.data->data);
            temp.level = Qnode->level+1;
            EnQueue(Q,&temp);
        }
        if(Qnode->data->rchild !=NULL){
            QElemType temp;
            temp.data = Qnode->data->rchild;
            temp.level = Qnode->level+1;
            EnQueue(Q,&temp);
        }
    }
    if(levelNum > maxNum){
        maxNum = levelNum;
    }
    printf("the res is %d\n",maxNum);
     return maxNum;
}




int main(){
    int preArr[MAXSIZE] = {1,2,4,5,7,3,6};
    int inArr[MAXSIZE] = {4,2,7,5,1,3,6}; 
    int levelArr[MAXSIZE] = {1,2,3,4,5,6,7}; 
    BiTree T =  createBiTree(preArr,0,6,inArr,0,6);
    BiTree T2 = createBiTree02(levelArr,0,6,inArr,0,6);
   getWeight(T2);
   // printf("\n");
  // operateFun(T);
 // initLinkNode(&T);
  // printf(" the res is %d\n",isSimilar(T,T2));
}
